[toc]
1.路由算法的分类
静态路由算法
- 最短路径算法（Dijkstra）：从起点开始沿着最短路径延申连接网络的各个节点，构成一棵树——汇集树
动态路由算法步骤
测量
- 收集网络拓扑信息
- 主要收集自己附近的信息
更新
- 把收集的信息通知到别的路由器
- 收到别人的信息要更新自己的数据库
- 计算
- 根据收集的信息计算路由表->转发表
2.动态路由算法
2.1 距离矢量算法——路由信息协议RIP
DV（Distance Vector Routing）算法要点：
- 仅和相邻路由器交换信息；
- 路由交换的内容是自己的路由表；
- 周期性更新30s；
RIP是内部网关协议IGP中最先得到广泛使用的协议之一，RIP要求自治系统AS的每一个路由器都要维护从它自己到AS内其他每一个网络的距离记录，称为距离向量D-V；
- 路由器到直连网络的距离：1；
- 路由器到非直连网络的距离：经过路由器数+1；
- 一条路径最多包含15个路由器，距离为16时表示目的不可达，所以RIP只适合小型网络；
RIP认为好的路由就是所通过路由器数量最少的路由，当到达同一目的的不同路径所经过的路由一样时，进行等价负载均衡策略，即是将通信量均衡的分布到多条等价的路由上
RIP包含以下要点：
- 和谁交换信息——相邻路由器
- 交换什么信息——自己的路由表
- 何时交换信息——周期性交换
基本工作过程：
- 路由器刚开始工作时，只知道自己相连的直连网络的距离为1
- 每个路由器只和自己相邻的路由器周期性的更新路由信息，更新规则如下：
- 同一目的网络、下一跳，代表是最新消息，虽然距离可能更长，但也要更新
- 新的路由条目，添加
- 同一目的网络，不同下一跳，新的路由信息距离更短，更新
- 同一目的网络，不同下一跳，等价负载均衡
- 同一目的网络，不同下一跳，新的路由信息距离更长，不更新
- 经过若干次更新，每个路由器都知道本AS内各网络的最短距离和下一跳地址，称为收敛；
RIP的“坏消息传播得慢”问题：
假设路由器R1和R2相连，R1的直连网络N1发生故障，R1检测到这个问题后，等到更新周期到了，就会发送一个（目的网络=N1，距离=16，下一跳=直连端口）的更新报文给R2，同时R2向R1发送（N1，2，R1）的更新报文，如果R2发送的报文更快到达，则R1会认为N1可以通过R2到达，R1就会向R2发送（N1，3，R2）的更新报文，R2收到后，就会更新报文（N1，4，R1），并且到下一个更新周期又发送给R1，一直重复R1->R2->R1的环路进行路由更新，直到发送（N1，16，R2）（N1，16，R1）
上述问题是距离向量的固有问题，解决办法如下：
- 限制最大路径距离15
- 进行“触发更新”，路由表发生更新立即发送更新报文，而不是周期性发送
- 路由器记录到某特定路由信息的接口，而不让同一路由信息再通过此接口向反方向传送（即“水平分割”）
2.2 链路状态路由算法——开放最短路径优先OSPF协议
基本思想：
- 测量——发现邻居，测量与邻居间链路的开销
- 更新——把链路信息发送给网络中其他所有网络，并建立自己的链路状态数据库->重构拓扑结构图
- 计算——根据最短路径算法计算汇集树->生成路由表
距离矢量算法要点：
- 和所有的路由器交换信息
- 路由器交换的内容是自己邻居链路信息
- 事件触发更新
OSPF采用FPS算法计算路由，所以不会出现路由环路问题
使用OSPF的每个路由都会产生链路状态通告（Link State Advertisement, LSA），LSA包括
- 直连网络的链路状态信息
- 邻居路由器的链路状态信息
LSA被封装在链路状态更新分组LSU中，采用泛洪发送
使用OSPF的每个路由都有一个链路状态数据库LSDB，用于存储LSA
通过各路由器泛洪发送封装有自己的LSA的LSU分组，各路由器的LSDB最终达到一致
OSPF的五种分组类型
- 问候分组（HELLO）分组
- 数据库描述（Database Description）分组
- 链路状态请求（Link State Request）分组
- 链路状态更新（Link State Update）分组
- 链路状态确认（Link State Acknowledgment）分组
发现邻居：启动路由器后，路由器向每个点到点的线路发送一个携带自己网络地址HELLO分组，另一端收到后发送回一个应答通报自己的网络地址
- HELLO分组封装在IP数据报中，发送到组播地址244.0.0.5
- 发送周期为10秒
- 40秒末未收到邻居路由器的HELLO分组，则认为邻居路由器不可达
| 源IP/路由器接口IP | 目的IP(244.0.0.5) | 协议号89 | OSPF首部 | OSPF分组载荷 |
| ————————- | ————————- | ———— | ———— | —————— |测量线路开销：路由器发送一个ECHO分组要求对方立刻响应，测量一个来回的时间再除以2就能得到一个延迟估计值，这个值就是该线路的开销，如果要求更精确可以多测几遍然后取平均值
构造分组：
假设每个节点的分组表如下，用（邻居，代价）来表示当且节点到邻居节点需要的代价（延迟，带宽，距离等决定）：
| A | B | C | D | E | F |
| —— | —— | —— | —— | —— | —— |
| 序号 | 序号 | 序号 | 序号 | 序号 | 序号 |
| 年龄 | 年龄 | 年龄 | 年龄 | 年龄 | 年龄 |
| B-4 | A-4 | B-2 | C-3 | A-5 | B-6 |
| E-5 | C-2 | D-3 | F-7 | C-1 | D-7 |
| | F-6 | E-1 | | F-8 | E-8 |发布链路状态分组
以B为例子，相邻路由器为A、C、F，如果节点E的链路状态分组经过A和F到达B，节点B必须再将E的状态分组发送给C，这是因为A和F已经收到了，而B的相邻节点C没有收到，所以向C发送，以此类推，就能够实现向所有的路由器交换信息，最后节点B发送链路状态表如下：
| 源 | 序号 | 年龄 | A | C | F | A | C | F | 数据 |
| —— | —— | —— | —— | —— | —— | —— | —— | —— | —— |
| A | 21 | 60 | 0 | 1 | 1 | 1 | 0 | 0 | |
| F | 21 | 60 | 1 | 1 | 0 | 0 | 0 | 1 | |
| E | 21 | 59 | 0 | 1 | 0 | 1 | 0 | 1 | |
| C | 20 | 60 | 1 | 0 | 1 | 0 | 1 | 0 | |
| D | 21 | 59 | 1 | 0 | 0 | 0 | 1 | 1 | |其中前三个A、C、F是发送标志，后三个为ACK标志.每一行表示从源A发送的状态分组到达B后，B向哪个节点转发.例如第一行，表示A发送状态分组到达B后，B向C,F发送，所以C，F的发送标志置为1，又B收到A的分组后要向A发送ACK确认，所以A的ACK标志置为1
后续工作
- 收集链路信息建立链路状态数据库LSDB
- 重构拓扑图
- 根据拓扑图运行最短路径优先算法（SPF）计算汇集树
- 计算路由表
问题：如果一个网络中每个路由器都两两相邻，那么邻居关系数量为$\Large\frac{n(n-1)}{2}$，每次更新都要向n-1个路由器发送LSU分组
解决方法：在网络中的路由器选举一个指定路由器（designated router）和备用的指定路由器（backup designated router），所有的非指定路由器只与指定路由器建立邻居关系，所以非DR/BDR之间通过DR/BDR来交换信息，若DR出现问题，则使用BDR。
为了使OSPF能够用于规模更大的网络，OSPF把一个自治系统在划分为若干个更小的范围，叫做区域（Area）
每个区域都有一个32比特的区域标识符，主干区域标识符必须为0，其他区域的标识符不能为0且不能相同，每个区域最好不要规模太大，不要超过200个路由器。这样就把泛洪交换信息限制在一个小的区域
在一个区域内的路由器叫做区域间路由器IR
为了本区域可以和该自治系统的其他区域连通，每个区域都有一个区域边界路由器ABR，它的一个接口连接自身所在的区域，另一个接口连接到主干区域
主干区域内的路由器称为主干路由器BBR
- 其中主干路由器中还要有一个使得本自治系统和其他自治系统交换路由信息的自治系统边界路由器ASBR
LSR的优点：
- 路由信息的一致性好，坏消息也一样传播的快
- 状态分组长度较短，传输所需要的网络带宽不大，适用于大型网络
LSR的缺点：
- 每个路由器都需要有较大的存储空间
- 计算量大，每次都必须计算最短路径
与距离矢量不同的是，距离矢量没有完整的拓扑图